package org.liaohailong.helloworld.study;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * Author: liaohailong
 * Date: 2021/4/29
 * Time: 21:00
 * Description:
 **/
public class BTree2 {
//    public Node connect(Node root) {
//        if (root == null) return null;
//
//        ArrayList<LinkedList<Node>> collect = new ArrayList<>();
//        collect(root, collect, 0);
//
//        Node head = null;
//        StringBuilder sb = new StringBuilder();
//        sb.append("[");
//        for (LinkedList<Node> nodes : collect) {
//            sb.append("[");
//            for (Node node : nodes) {
//                if (head == null) {
//                    head = node;
//                } else {
//                    head.next = node;
//                    head = head.next;
//                }
//                sb.append(node.val);
//                sb.append(",");
//            }
//            if (head != null) {
//                head.next = null;
//                head = null;
//            }
//            sb.deleteCharAt(sb.length() - 1);
//            sb.append("]");
//            sb.append(",");
//        }
//        sb.deleteCharAt(sb.length() - 1);
//        sb.append("]");
//        System.out.println(sb);
//
//        return root;
//    }
//
//    private void collect(Node node, ArrayList<LinkedList<Node>> collect, int index) {
//        if (node == null) return;
//
//        LinkedList<Node> indexNodeList;
//        if (collect.size() <= index) {
//            indexNodeList = new LinkedList<>();
//            collect.add(index, indexNodeList);
//        } else {
//            indexNodeList = collect.get(index);
//        }
//
//        indexNodeList.addLast(node);
//
//        index++;
//        collect(node.left, collect, index);
//        collect(node.right, collect, index);
//    }

//    public Node connect(Node root) {
//        if (root == null) return null;
//        traversal(root.left, root.right);
//        return root;
//    }

//    private void traversal(Node left, Node right) {
//        if (left == null) return;
//        left.next = right;
//
//        traversal(left.left, left.right);
//        if (right != null) {
//            traversal(left.right, right.left);
//            traversal(right.left, right.right);
//        }
//    }

    public Node connect(Node root) {
        if (root == null) return null;
        if (root.left != null) {
            if (root.right != null) {
                root.left.next = root.right;
            } else
                root.left.next = getNext(root.next);
        }
        if (root.right != null) {
            root.right.next = getNext(root.next);
        }

        connect(root.right);
        connect(root.left);
        return root;
    }

    // 父节点的next节点如果有值（叔伯），就可以找到同level层节点（堂兄弟）
    private Node getNext(Node parent) {
        if (parent == null) return null;
        System.out.println("get next parent = " + parent.val);
        if (parent.left != null) {
            System.out.println("get next parent left " + parent.left.val);
            return parent.left;
        }
        if (parent.right != null) {
            System.out.println("get next parent right " + parent.right.val);
            return parent.right;
        }
        System.out.println("get next parent next " + parent.next);
        return getNext(parent.next); // 右侧的节点（小叔叔）
    }

    // LC 打开转盘锁
    // https://leetcode-cn.com/leetbook/read/queue-stack/kj48j/
    public int openLock(String[] deadends, String target) {
        Set<String> forbidden = new HashSet<>(Arrays.asList(deadends));
        String root = "0000";
        // 命中第一个值，直接锁死了
        if (forbidden.contains(root)) return -1;

        // 访问者，防止重复内容出现
        Set<String> visitor = new HashSet<>();

        // BFS遍历
        LinkedList<String> list = new LinkedList<>();
        list.add(root);
        // 树深度，即拨动次数
        int depth = 0;
        while (!list.isEmpty()) {
            // 本层的节点个数
            int size = list.size();
            // 一层一层遍历
            while (size > 0) {
                size--;
                String node = list.pollFirst();
                // 已经找到，返回深度，就是拨动轮盘最小次数
                if (node.equals(target)) return depth;

                for (int i = 0; i < node.length(); i++) {
                    char c = node.charAt(i);

                    // add
                    String add = node.substring(0, i) + (c == '9' ? 0 : c - '0' + 1) + node.substring(i + 1);
                    // subtract
                    String sub = node.substring(0, i) + (c == '0' ? 9 : c - '0' - 1) + node.substring(i + 1);

                    // 加一位数字，不重复出现，并且没在死亡数字内
                    if (!visitor.contains(add) && !forbidden.contains(add)) {
                        visitor.add(add);
                        list.addLast(add);
                    }
                    // 减一位数字，不重复出现，并且没在死亡数字内
                    if (!visitor.contains(sub) && !forbidden.contains(sub)) {
                        visitor.add(sub);
                        list.addLast(sub);
                    }
                }
            }
            depth++;
        }

        return -1;
    }

    // LC 完全平方数
    // https://leetcode-cn.com/leetbook/read/queue-stack/kfgtt/
    public int numSquares(int n) {
        if (n <= 0) return 0;
        if (n <= 1) return 1;

        // 去重复
        Set<Integer> visitor = new HashSet<>();
        // BFS
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(0);
        int depth = 0;
        while (!list.isEmpty()) {
            depth++;
            // 每一层树的数量
            int size = list.size();
            while (size-- > 0) {
                Integer parent = list.pollFirst();

                int i = 1;
                int total = 0;
                while (total < n) {
                    int temp = i * i;
                    total = parent + temp;
                    if (total < n) {
                        // 去除重复数字
                        if (!visitor.contains(total)) {
                            visitor.add(total);
                            list.addLast(total);
                        }
                        i++;
                    } else if (total == n) {
                        return depth;// 找到了最短路径
                    } else break;
                }
            }
        }

        return depth;
    }

    // Definition for a Node.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}
